/*
题目: 对链表进行插入排序
https://leetcode.cn/problems/insertion-sort-list/
 */
public class InsertionSortList {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(-66666, head);

        // 对 head.next 进行插入
        // 插入排序本质上 就是 把 tar 放到第一个大于它 的前面
        while (head != null && head.next != null) {
            if (head.val <= head.next.val) {
                head = head.next;
                continue ;
            }

            // 每次从前面 开始找, 找第一个大于 自己的 结点
            ListNode prev = dummy;
            while (prev.next.val <= head.next.val) {
                prev = prev.next;
            }

            ListNode tmp = head.next;
            head.next = head.next.next;
            tmp.next = prev.next;
            prev.next = tmp;

            // head = head.next; 这里不需要在 往下迭代了, 因为 此时 head 和 head.next 还没判断
        }

        return dummy.next;
    }
}
